#include<iostream>
using namespace std;
using ll = long long;
ll L;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll qmul(ll a, ll k, ll p)
{
    ll res = 0;
    while (k)
    {
        if (k & 1) res = (res + a) % p;
        a = (a + a) % p;
        k >>= 1;
    }
    return res;
}
ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = qmul(res, a, p);
        a = qmul(a, a, p);
        k >>= 1;
    }
    return res;
}
ll get_euler(ll c)
{
    ll res = c;
    for (ll i = 2; i <= c / i; i++)
    {
        if (c % i == 0)
        {
            while (c % i == 0) c /= i;
            res = res / i * (i - 1);
        }
    }
    if (c > 1) res = res / c * (c - 1);
    return res;
}
int main()
{
    int t = 0;
    while (cin >> L, L)
    {
        ll d = gcd(L, 8);
        ll c = 9 * L / d;
        ll res = 1e18;
        if (gcd(10, c) != 1) res = 0;
        else
        {
            ll phi = get_euler(c);
            for (ll i = 1; i <= phi / i; i++)
            {
                if (phi % i == 0)
                {
                    if (qmi(10, i, c) == 1) res = min(res, i);
                    if (qmi(10, phi / i, c) == 1) res = min(res, phi / i);
                }
            }
        }
        cout << "Case " << ++t << ": " << res << endl;
    }
    return 0;
}